"""
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

236. 二叉树的最近公共祖先
已解答
中等
相关标签
premium lock icon
相关企业
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 

示例 1：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1
 

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from typing import List
from tree_node import TreeNode,build_tree_node

class Solution:

    """
    由于给出的二叉树的子节点，无法回溯至其父节点。因此，归根结底，还是应该依赖于root对各节点的遍历，以便找到父级关系

    可分别补录各项，创建一个节点链，直到分别与两个子节点匹配一致。

    之后对比两个节点的共同前缀即可。


    方案可行，但逻辑有点复杂。
    优点是：有利于以后任意两个节点的比较，而不需要再做前置工作
    缺点是：其实可以把逻辑搞得再简单点
    
    """

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        path_temp:List[List[TreeNode]]=[[root]]
        total_paths:List[List[TreeNode]]=[]
        while path_temp:
            total_paths.extend(path_temp[::])
            new_path_temp:List[List[TreeNode]]=[]
            for nodes in path_temp:
                if nodes[-1].left:
                    new_path_temp.append(nodes+[nodes[-1].left])
                if nodes[-1].right:
                    new_path_temp.append(nodes+[nodes[-1].right])
            path_temp=new_path_temp
        
        p_path=None
        q_path=None
        for path in total_paths:
            if p_path and q_path:
                break
            if path[-1]==p:
                p_path=path
            if path[-1]==q:
                q_path=path

        res=None
        for i in range(min(len(p_path),len(q_path))):
            if p_path[i]==q_path[i]:
                res=p_path[i]
            else:
                break

        return res
    
if __name__=='__main__':
    arr=[3,5,1,6,2,0,8,None,None,7,4]
    root=build_tree_node(arr)
    p=root.left
    q=root.right
    s=Solution()
    res=s.lowestCommonAncestor(root,p,q)
    print(res.val)
            